package org.example.tree.utils;

import org.example.tree.entity.BinaryTreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zjt
 * @description
 * @date 2024/1/30 10:25
 */
public class BinaryTreeUtil {

    /**
     * 获取树中节点的个数
     */
    public static int nodeSize = 0;

    public int size(BinaryTreeNode binaryTreeNode) {
        if (binaryTreeNode == null) {
            return 0;
        }
        nodeSize++;
        size(binaryTreeNode.left);
        size(binaryTreeNode.right);
        return nodeSize;
    }

    public int size2(BinaryTreeNode binaryTreeNode) {
        if (binaryTreeNode == null) {
            return 0;
        }
        return size2(binaryTreeNode.left) + size2((binaryTreeNode.right)) + 1;
    }

    /**
     * 获取叶子节点的个数
     *
     * @param binaryTreeNode
     * @return
     */
    public int getLeafNodeCount(BinaryTreeNode binaryTreeNode) {
        if (binaryTreeNode == null) {
            return 0;
        }
        if (binaryTreeNode.left == null && binaryTreeNode.right == null) {
            return 1;
        }
        return getLeafNodeCount(binaryTreeNode.left) + getLeafNodeCount(binaryTreeNode.right);
    }

    /**
     * 获取第K层节点的个数
     * 相对于根节点，就是获取左数的第K-1层 + 右数的第K-1层
     *
     * @param binaryTreeNode
     * @param K
     * @return
     */
    int getKLevelNodeCount(BinaryTreeNode binaryTreeNode, int K) {
        if (binaryTreeNode == null || K <= 0) {
            return 0;
        }
        if (K == 1) {
            return 1;
        }
        return getKLevelNodeCount(binaryTreeNode.left, K - 1) + getKLevelNodeCount(binaryTreeNode.right, K - 1);
    }

    /**
     * 获取二叉树的高度
     *
     * @param binaryTreeNode
     * @return
     */
    int getHeight(BinaryTreeNode binaryTreeNode) {
        if (binaryTreeNode == null) {
            return 0;
        }
        return Math.max(getHeight(binaryTreeNode.left), getHeight(binaryTreeNode.right)) + 1;
    }

    /**
     * 检测值为value的元素是否存在
     *
     * @param binaryTreeNode
     * @param val
     * @return
     */
    public BinaryTreeNode find(BinaryTreeNode binaryTreeNode, int val) {
        if (binaryTreeNode == null) {
            return null;
        }

        if (binaryTreeNode.root == val) {
            return binaryTreeNode;
        }

        BinaryTreeNode ret1 = find(binaryTreeNode.left, val);
        if (ret1 != null) {
            return ret1;
        }
        BinaryTreeNode ret2 = find(binaryTreeNode.right, val);
        if (ret2 != null) {
            return ret2;
        }
        return null;
    }


    /**
     * 判断一棵树是不是完全二叉树
     *
     * @param binaryTreeNode
     * @return
     */
    public boolean isCompleteTree(BinaryTreeNode binaryTreeNode) {
        Queue<BinaryTreeNode> queue = new LinkedList<>();

        if (binaryTreeNode == null) {
            return true;
        }
        queue.offer(binaryTreeNode);
        while (!queue.isEmpty()) {
            BinaryTreeNode node = queue.poll();
            if (node != null) {
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                break;
            }
        }
        // 判断剩下的值是否有不为空的
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;
    }
}
